//
// Created by yanhai on 2021/1/7.
//

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int KEY_VALUE;

#define BSTREE_ENTRY(name, type) \
    struct name {                \
        struct type *left;       \
        struct type *rigth;      \
    }

struct bstree_node {
    KEY_VALUE data;
    BSTREE_ENTRY(, bstree_node) bst;
};

struct bstree {
    struct bstree_node *root;
};

/**
 * \brief 创建一个节点
 * \param key
 * \return
 */
struct bstree_node *bstree_create_node(KEY_VALUE key)
{
    struct bstree_node *node = (struct bstree_node *) malloc(sizeof(struct bstree_node));
    if (node == NULL) {
        assert(0);
    }
    node->data = key;
    node->bst.left = node->bst.rigth = NULL;
    return node;
}

/**
 * \brief 插入一个节点
 * \param T
 * \param key
 */
void bstree_insert(struct bstree *T, int key)
{
    assert(T != NULL);

    if (T->root == NULL) {
        T->root = bstree_create_node(key);
        return;
    }

    // 使用node一直向下比较，直到是叶子节点
    // node_parent是node的父节点
    // 默认开始时都是根节点
    struct bstree_node *node = T->root;
    struct bstree_node *node_parent = T->root;

    while (node != NULL) {
        node_parent = node;
        if (key < node->data) {     // 要插入的数据比node小，向左子树遍历
            node = node->bst.left;
        } else {
            node = node->bst.rigth; // 要插入的数据比node大，向右子树遍历
        }
    }

    // 此时node是叶子节点了，我们就是要把要插入的key节点，放在这个node叶子节点上面
    // 由于我们无法通过子节点找到其父节点，因此我们要实时保存node的父节点，
    // 这也是node_parent存在的意义。
    if (key < node_parent->data) {
        node_parent->bst.left = bstree_create_node(key);
    } else {
        node_parent->bst.rigth = bstree_create_node(key);
    }
}

/**
 * \brief 使用中序遍历，可以有序的打印出所有节点
 * \param node
 */
void bstree_traversal(struct bstree_node *node)
{
    if (node != NULL) {
        bstree_traversal(node->bst.left);
        printf("%4d", node->data);
        bstree_traversal(node->bst.rigth);
    }
}

int main()
{
#define ARRAY_LENGTH    20
    int keyArray[ARRAY_LENGTH] = {24, 25, 13, 35, 23, 26, 67, 47, 38, 98, 20, 13, 17, 49, 12, 21, 9, 18, 14, 15};

    struct bstree T = {0};
    for (int i = 0; i < ARRAY_LENGTH; i++) {
        bstree_insert(&T, keyArray[i]);
    }

    bstree_traversal(T.root);

    printf("\n");
    return 0;
}
